package red.book._2._1;

import java.util.Arrays;

public class ShellSort {
	public static void sort(Comparable[] a) { // Sort a[] into increasing order.
		int N = a.length;
		int h = 1;
		while (h < N / 3)
			h = 3 * h + 1; // 1, 4, 13, 40, 121, 364, 1093, ...
		while (h >= 1) { // h-sort the array.
			for (int i = h; i < N; i++) { // Insert a[i] among a[i-h], a[i-2*h], a[i-3*h]... .
				for (int j = i; j >= h && Example.less(a[j], a[j - h]); j -= h) {
					Example.exch(a, j, j - h);
				}
				System.out.println("间隔：" + h + "\t数组内容：" + Arrays.toString(a));
			}
			h = h / 3;
		}
	}
	// See page 245 for less(), exch(), isSorted(), and main().
	
	public static void main(String[] args) {
		Comparable[] a = new Comparable[] {'S', 'H', 'E', 'L', 'L', 'S', 'O', 'R', 'T', 'E', 'X', 'A', 'M', 'P', 'L', 'E'};
		sort(a);
	}
}
